package binarytree

/*
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
*/

// 输入：nums = [-10,-3,0,5,9]
// 输出：[0,-3,9,-10,null,5]

// 自己做的
// 用时 0ms 100%
// 内存消耗 3.4mb 87.45%
func SortedArrayToBSTByMySelf(nums []int) *TreeNode {

	nLength := len(nums)
	nCenter := nLength / 2

	var father = new(TreeNode)

	if nLength == 1 {
		father.Val = nums[0]
		father.Left = nil
		father.Right = nil
		return father
	}
	father.Val = nums[nCenter]

	// mid 不在端点
	if nCenter < nLength-1 && nCenter > 0 {
		numsRight := nums[nCenter+1 : nLength : nLength]
		numsLeft := nums[0:nCenter:nLength]
		father.Left = SortedArrayToBSTByMySelf(numsLeft)
		father.Right = SortedArrayToBSTByMySelf(numsRight)
	} else if nCenter == nLength-1 { // mid在右端点
		numsLeft := nums[0:nCenter:nLength]
		father.Left = SortedArrayToBSTByMySelf(numsLeft)
		father.Right = nil
	} else if nCenter == 0 { // mid在左端点
		numsRight := nums[nCenter+1 : nLength : nLength]
		father.Left = nil
		father.Right = SortedArrayToBSTByMySelf(numsRight)
	}
	return father
}

// 效果与自己写的差不多，官方答案都是递归 大同小异
func sortedArrayToBST(nums []int) *TreeNode {
	return helper(nums, 0, len(nums)-1)
}

func helper(nums []int, left, right int) *TreeNode {
	if left > right {
		return nil
	}
	mid := (left + right) / 2
	root := &TreeNode{Val: nums[mid]}
	root.Left = helper(nums, left, mid-1)
	root.Right = helper(nums, mid+1, right)
	return root
}
